1. Field of the Invention
The present invention relates to a method of reliably and robustly encoding data streams to be transmitted to various types of communication and computer systems, for example but not limited to, a one-way satellite broadcast system including a host computer and a subscriber computer. In particular, the present invention relates to an encoding procedure that uses a shifted interleaving of packets.
2. Description of Related Art
U.S. Pat. No. 6,609,223, U.S. Pat. No. 6,012,159, and U.S. Pat. No. 6,272,658, all of which are assigned to KenCast, Inc., are hereby incorporated by reference.
U.S. Pat. No. 6,609,223 describes a method for encoding a stream of source packets, in which a number, k, of source packets of a message are packet-level forward-error-correction (“FEC”) encoded to form a number n−k of error-correcting wildcard packets. The k source packets and the n−k wildcard packets (forming a total of n packets) are to be transmitted by a transmitter/encoder, such as a host computer, to a receiver/decoder, such as a subscriber computer. The message may be successfully reconstructed on the receiver/decoder side as long as any of k packets, whether they are source packets or wildcard packets or both, are successfully received. For example, a transmitted message may comprise k=180 source packets and n−k=20 wildcard packets, for a total of n=200 transmitted packets, as shown in FIG. 1A of U.S. Pat. No. 6,609,223 and reproduced herein as FIG. 1A. As long as any of 180 packets are successfully received by the receiver/decoder, the message of the 180 source packets may be reconstructed from the successfully received packets.
As disclosed in U.S. Pat. No. 6,609,223, after the arrival of each source packet at the transmitter/encoder, for each byte of the source packet, the respective error-correction contributions to the corresponding bytes of the n−k wildcard packets are computed. Thereafter, the source packet is transmitted to the receiver/decoder without waiting for the arrival of another source packet of the k source packets. This is repeated for each arriving source packet. For each wildcard packet byte, the error-correction contribution generated from each source packet is summed in an accumulator, or the like. After all the error-correction contributions have been computed using all k source packets and summed over all n−k wildcard packets, the wildcard packets are transmitted to the receiver/decoder.
As further disclosed in U.S. Pat. No. 6,609,223, the number n−k of wildcard packets is determined by the operator of the transmitter/encoder (e.g., host computer), based on knowledge of the communication channel to be used, and, specifically, on the expected number of packets to be lost during transmission, e.g., due to interference. For example, it may be expected that a maximum 4 out of 16 transmitted packets will be lost during transmission, a 25% loss rate, and thus n−k=4 wildcard packets will be computed for every k=12 source packets. (A 25% loss rate was chosen to provide an easy to understand example—actual loss rates usually are less than 5%. In any event, the present invention is not limited to any particular loss rate.) Accordingly, at the receiver/decoder, the k=12 source packets may be reconstructed without errors if any 12 of the transmitted packets, that is, any combination of transmitted source packets and wildcard packets, are successfully received.
U.S. Pat. No. 6,609,223 explains that due to the nature of actual packet streams not all expected source packets may arrive at the transmitter/encoder. Continuing with the above example, only the first nine of the expected twelve source packets may arrive at the transmitter/encoder; the last three may never arrive. Eventually, a timeout condition occurs, for example, after the elapse of a predetermined time interval from the arrival of the last source packet (this generally is referred to as the “timeout case,” in contrast to the case where all expected source packets arrive). At that time, i.e., when a timeout condition occurs, the wildcard packets, and more preferably, a subset thereof, are transmitted, with an indication in the headers of the wildcard packets that, in this example, only nine source packets contributed to the information of the wildcard packets.
As also disclosed in U.S. Pat. No. 6,609,223 (and, by reference therein, U.S. Pat. No. 6,012,159 and U.S. Pat. No. 6,272,658), to further enhance the encoding scheme's robustness against interference, prior to encoding and transmission, the packets may be grouped into multiple shares in an interleaving fashion, as shown in FIG. 1B of U.S. Pat. No. 6,609,223 reproduced herein as FIG. 1B. In FIG. 1B, the odd-numbered source packets and wildcard packets comprise Share 1, while the even-number source packets and wildcard packets comprise Share 2.
Further, U.S. Pat. No. 6,609,223 discloses that a lot of multiple shares of interleaved packets may be transmitted to a subscriber computer at the same time. That is, one share of interleaved packets may be transmitted to the subscriber computer at the same time as several other shares of interleaved packets.
However, this arrangement has consequences. First, when the lot of multiple shares of interleaved packets is transmitted at the same time, all of the shares in the lot are received and ready for decoding at the subscriber computer at approximately the same time. As the number of shares per lot increases, the amount of computation required for decoding each lot increases linearly, and the time in between such computations increases linearly. Another consequence of this arrangement is that the number of error-correcting wildcard packets that must be (consecutively) transmitted at a given time increases linearly with the number of shares per lot. It would desirable to have an encoding method that overcomes these consequences.